波卡的共识（进阶版）
区块链节点使用共识引擎在区块链状态上达成统一。本文介绍了区块链系统中共识的基本原理，共识如何与 Substrate 框架中的 runtime 交互，以及框架中可用的共识引擎。
状态机和冲突
区块链 runtime 是一个状态机[1]。它有一些内部状态和状态转换功能，允许它从当前状态转换到未来状态。在大多数 runtime 中，有些状态具有到多个未来状态的有效转换，但必须选择一个转换。
区块链必须在以下几方面达成一致：
一些初始状态，叫做“创世” 一系列的状态转换，每个都称为“区块” 最终（当前）状态
为了对转换后的结果状态达成一致，区块链的状态转换功能[2]中的所有操作都必须是确定性的。
冲突排除
在中心化系统中，中心化的权限通过按照他们看到的顺序记录状态转换，在相互排斥的备选方案中进行选择，并在发生冲突时选择竞争备选方案中的第一个。在去中心化系统中，节点将看到不同顺序的交易，因此它们必须使用更精细的方法来排除交易。更复杂的是，区块链网络力求容错，这意味着即使某些参与者不遵守规则，系统也应继续提供共识的数据。
区块链将交易批处理成区块，并有一些方法来选择哪个参与者有权提交区块。例如，在 PoW 链中，首先找到有效工作证明的节点有权向链提交块。
Substrate 提供多种区块构造算法，还允许你创建自己的：
Aura (Round Robin) BABE (基于插槽) PoW
分叉选择的规则
作为一个基元，区块包含一个区块头和一批外部对象[3]。区块头必须包含对其父块的引用，以便可以跟踪链的起源。当两个区块引用同一父块时，会发生分叉。必须解决分叉，以便只存在一个规范链。
分叉选择规则是一种算法，它获取一个区块链并选择“最佳”链，从而选择应该扩展的链。Substrate 通过 SelectChain 展现了这个概念。
Substrate 允许你编写一个自定义的分叉选择规则，或使用一个现成的。例如：
最长链规则
最长链规则简单地说，最好的链就是最长的链。Substrate 用LongestChain 结构提供这个链选择规则。GRANDPA 用最长链规则进行投票。
GHOST 规则
GHOST 规则就是，从创世块开始，通过递归地选择在其上构建块最多的分支来解决每个分叉。
区块生产
区块链网络中的某些节点能够生成新的区块，这一过程称为 authoring。具体哪些节点可以编写区块取决于你使用的共识引擎。在一个中心化的网络中，一个节点就可以编写所有的区块，而在完全无权限的网络中，算法必须在每个高度选择区块的生产者。
PoW
在像比特币这样的 PoW 系统中，任何节点都可以在任何时候生成一个块，只要它解决了计算密集的问题。解决这个问题需要 CPU 时间，因此矿工只能根据计算资源的比例生成块。
Substrate 提供了一个 PoW 块生产引擎。
插槽
基于插槽的共识算法必须有一组已知的验证人，这些验证人可以生成块。时间被分配到不同的插槽中，在每个插槽中只有一些验证人可以产生块。在每个插槽中，验证人可以编写块的细节因引擎而异。Substrate 提供 Aura 和 Babe，这两个都是基于插槽的区块生产引擎。
最终性
任何系统中的用户都想知道他们的交易何时完成，区块链也不例外。在一些传统的系统中，最终性发生在收据被移交或文件被签署时。
使用到目前为止描述的区块生产方案和分叉选择规则，交易永远不会完全完成。总有一个机会，一个较长（或较重）的链将出现，并恢复你的交易。然而，在一个特定的块上构建的块越多，它被还原的可能性就越小。这样，块生产和适当的分叉选择规则提供了概率的最终性。
当需要确定的最终性时，可以向区块链的逻辑中添加一个终结性小工具。一个固定权限集的成员铸造最终性的投票，当对某个区块投了足够的票时，该区块被视为最终的。在大多数系统中，这个阈值是 2/3。如果没有外部协调（如硬分叉），由此类小工具完成的块将无法恢复。
“一些共识系统将出块和最终性联系在一起，例如，最终性是出块过程的一部分，在块 N 完成之前，不能生成新的块 N+1。然而，Substrate 分离了这两个过程，并可以单独使用任何具有概率终结性的出块引擎，或者将其与最终性小工具耦合以获得确定性的最终性。
在使用最终性小工具的系统中，必须修改分叉选择规则以考虑最终性游戏的结果。例如，节点将选择包含最近完成的块的最长链，而不是选择最长链的周期。
Substrate 中的共识
Substrate 框架附带了几个共识引擎，这些引擎提供了块生产或最终性。本文简要概述了 Substrate 本身自带的产品。欢迎开发者提供自己的定制共识算法。
Aura
Aura[4] 提供基于插槽的块生产机制。在 Aura 中，一个已知的权限集轮流出块。
BABE
BABE[5] 是通过一组已知验证人的基于插槽的块生产共识。在这些方面它类似于 Aura。与 Aura 不同，插槽分配基于可验证随机函数（VRF）的评估。为每个验证人分配一个 epoch 的 weight。这个 epoch 被分成多个插槽，验证人在每个插槽计算它的 VRF。对于验证人的 VRF 输出低于其 weight 的每个插槽，允许生成一个块。
因为多个验证人可能会在同一个插槽中产生一个块，所以分叉在 BABE 中比在 Aura 中更常见，即使在良好的网络条件下也很常见。
当在给定的插槽内没有区块的生产者时，Substrate 的 BABE 实现也有一个后备机制。这些 “次要” 插槽分配允许 BABE 获得恒定的区块时间。
PoW
PoW 块的生产不是基于插槽的，也不需要已知的权限集。在 PoW 中，任何人都可以在任何时候生成一个块，只要他们能够解决一个具有计算挑战性的问题（通常是找出哈希原像）。这个问题的难度可以调整为提供一个统计目标块时间。
GRANDPA
GRANDPA[6] 提供区块的最终性。它有一个像 BABE 一样的已知 weight 的权限集。然而，GRANDPA 并不生产块，它只听取由生产引擎（比如上面三种）生成的块的“八卦”。GRANDPA 验证人在链上投票，而不是在区块上投票，也就是说，他们投票给一个他们认为“最好”的区块，并且他们的投票可以传递地应用到之前的所有区块。一旦超过三分之二的 GRANDPA 权限者投票支持某一特定区块，它就被认为是最终的。
与 Runtime 协调
最简单的静态共识算法完全在 runtime 之外工作，正如我们目前所描述的那样。然而，许多共识游戏通过添加需要与 runtime 协调的功能而变得更加强大。例如，包括 PoW 中的可调难度、权威证明中的权限轮换以及 PoS 网络中的基于 stake 的权重。
为了适应这些共识特征，Substrate 有一个 DigestItem 的概念，一个从节点的外部（共识所在的地方）传递到 runtime 的消息，反之亦然。
了解更多
因为 BABE 和 GRANDPA 都在波卡网络中使用，Web3 基金会提供了研究级别的算法演示。
BABE Research[7] GRANDPA Research[8]
所有确定性的最终性算法，包括 GRANDPA，都需要至少 2f + 1 个非故障节点，其中 f 是故障或恶意节点的数量。你可以在有缺陷的情况下达成一致[9]的开创性论文或维基百科：拜占庭错误[10]中，了解更多关于这个门槛的来源以及为什么它是理想的。
并非所有的共识协议都定义了一个单一的规范链。当具有相同父块的两个块没有冲突的状态更改时，一些协议验证有向无环图[11]（DAG）。
原文：https://substrate.dev/docs/en/knowledgebase/advanced/consensus
翻译：PolkaWorld 社区
参考链接
[1]状态机: https://en.wikipedia.org/wiki/Finite-state_machine
[2]状态转换功能: https://substrate.dev/docs/en/knowledgebase/runtime/index
[3]外部对象: https://substrate.dev/docs/en/knowledgebase/learn-substrate/extrinsics
[4]Aura: https://crates.parity.io/sc_consensus_aura/index.html
[5]BABE: https://crates.parity.io/sc_consensus_babe/index.html
[6]GRANDPA: https://crates.parity.io/sc_finality_grandpa/index.html
[7]BABE Research: https://research.web3.foundation/en/latest/polkadot/BABE/Babe.html
[8]GRANDPA Research: https://research.web3.foundation/en/latest/polkadot/GRANDPA.html
[9]缺陷的情况下达成一致: https://lamport.azurewebsites.net/pubs/reaching.pdf
[10]维基百科：拜占庭错误: https://en.wikipedia.org/wiki/Byzantine_fault
[11]有向无环图: https://en.wikipedia.org/wiki/Directed_acyclic_graph
更多内容：
扫码关注公众号，回复 “1” 加入波卡群
关注 PolkaWorld
发现 Web 3.0 时代新机遇
点个 “在看” 再走吧！